/*
  解法：快慢指针 + 一个额外的指针
  为什么：快慢指针判断是否有环（相遇则存在环）
		  快慢指针相遇后
		  从头再设置一个指针，与 slow 同时一步步走，相遇点即为环的起始节点
		  Leetcode题解解释了为什么
  
  时间复杂度：O(n)，空间复杂度：O(1)
 */

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

// 定义链表节点结构体
struct ListNode
{
	int val;
	ListNode *next;
	
	ListNode(int x) : val(x), next(NULL) {}
};

class Solution
{
public:
	ListNode *detectCycle(ListNode *head)
	{
		if (head == NULL || head->next == NULL)
		{
			return NULL;		//链表为空 或 链表只有一个节点
		}
		
		ListNode *fast = head;
		ListNode *slow = head;
		
		// 第一步：判断链表是否有环，即不是直链
		while (fast != NULL && fast->next != NULL)
		{
			slow = slow->next;
			fast = fast->next->next;
			
			if (slow == fast)				//链表有环
			{
				// 第二步：找到入口
				ListNode *entry = head;
				
				while (entry != slow)		//如果链表有环，指针entry和slow一定会在环的入口处相遇
				{
					entry = entry->next;
					slow = slow->next;
				}
				
				return entry;
			}
		}
		
		return NULL;
	}
};

// ======== 辅助函数：构造带环链表 ========
ListNode *createCycleList(vector<int> vals, int pos)
{
	if (vals.empty())
	{
		return NULL;
	}
	
	ListNode *head = new ListNode(vals[0]);
	ListNode *curr = head;
	ListNode *cycle_entry = NULL;
	
	for (int i = 1; i < (int)vals.size(); i++)
	{
		curr->next = new ListNode(vals[i]);
		curr = curr->next;
		
		if (i == pos)
		{
			cycle_entry = curr;
		}
	}
	
	if (pos == 0)
	{
		cycle_entry = head;
	}
	
	if (pos != -1)
	{
		curr->next = cycle_entry;
	}
	
	return head;
}

// ======== 主函数 ========
int main()
{
	Solution solution;
	
	// 示例输入：head = [3,2,0,-4], pos = 1
	vector<int> vals = {3, 2, 0, -4};
	int pos = 1;
	
	ListNode *head = createCycleList(vals, pos);
	ListNode *res = solution.detectCycle(head);
	
	if (res)
	{
		cout << "Cycle detected at node with value: " << res->val << endl;
	}
	else
	{
		cout << "No cycle detected." << endl;
	}
	
	return 0;
}


